/**
 * @author 雷明浩
 * @date 2025/7/3 11:23
 */
public class Nqueen {
    // N皇后
    // https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    // 记录列
    private boolean[] vis1;
    // 记录正交线
    private boolean[] vis2;
    // 记录反交线
    private boolean[] vis3;
    private int ret;
    public int Nqueen (int n) {
        // write code here
        vis1 = new boolean[n];
        vis2 = new boolean[2*n];
        vis3 = new boolean[2*n];
        ret = 0;
        dfs(n, 0);
        return ret;
    }

    private void dfs(int n, int row) {
        if (row >= n) {
            ret++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!vis1[col] && !vis2[col-row+n] && !vis3[row+col]) {
                vis1[col] = true;
                vis2[col-row+n] = true;
                vis3[row+col] = true;
                dfs(n, row+1);
                vis1[col] = false;
                vis2[col-row+n] = false;
                vis3[row+col] = false;
            }
        }
    }
}